package com.hfb.mashibing.alip8.diamondsquarealgorithm.class03;

import com.hfb.mashibing.alip8.util.ArrayUtils;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 问题：找到第k小的数
 *
 * 同：Code05_Bfprt.java
 */

public class Code01_FindMinKth {

    public static class MaxHeapComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }

    // 利用最大根堆，时间复杂度O(N*logK)
    public static int minKth1(int[] arr,int k) {
        PriorityQueue<Integer> maxHead = new PriorityQueue<>(new MaxHeapComparator());
        for (int i = 0; i < k; i++) {
            maxHead.add(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if(arr[i]<maxHead.peek()){
                maxHead.poll();
                maxHead.add(arr[i]);
            }
        }
        return maxHead.peek();
    }
    // 改写快排，时间复杂度O(N)
    public static int minKth2(int[] a,int k) {
        int[] arr = copyArray(a);
        return process2(arr, 0,arr.length-1,k-1);
    }
    public static int[] copyArray(int[] arr) {
        int[] ans = new int[arr.length];
        for (int i = 0; i != ans.length; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }

    // 在arr中，找第K小的数:process2(arr,0,N-1,k-1)
    // arr[L...R]范围上，如果排序的话（而非真实去排序）， 找位于index的数
    // index[L...R]
    public static int process2(int arr[], int L, int R, int index) {
        if (L == R) {   // L==R==index
            return arr[L];
        }
        // 不止一个数时，随机在 L+[0,R-L]取一个数
        int pivot = arr[L + (int) (Math.random() * (R - L + 1))];

        // 利用荷兰国旗问题，做划分。即：目标值在哪个范围内
        // L.......R        pivot
        // 0      10000     70...800    range={70, 800}
        int[] range = partition(arr, L, R, pivot);

        if (index >= range[0] && index <= range[1]) {
            return arr[index];
        } else if (index < range[0]) {
            return process2(arr, L, range[0] - 1, index);
        } else {
            return process2(arr, range[1], R, index);
        }
    }

    /**
     * 荷兰国旗问题
     *
     * @param arr
     * @param L
     * @param R
     * @param pivot
     * @return int[0, 1]
     */
    private static int[] partition(int[] arr, int L, int R, int pivot) {
        int less = L - 1;
        int more = R + 1;
        int cur = L;
        while (cur < more) {
            if (arr[cur] < pivot) {
                ArrayUtils.exchangeElements(arr, ++less, cur++);
            } else if (arr[cur] > pivot) {
                ArrayUtils.exchangeElements(arr, cur, --more);
            } else {
                cur++;
            }
        }
        return new int[]{less+1,more-1};
    }
    public static int minKth3(int[] a, int k){
        int[] arr = copyArray(a);
        return bfprt(arr,0,arr.length-1,k-1);
    }
    // bfprt算法，时间复杂度O(N）
    private static int bfprt(int[] arr, int L, int R, int index) {
        if (L == R) {
            return arr[L];
        }
        int pivot = medianOfMedians(arr, L, R);
        int[] range = partition(arr, L, R, pivot);
        if (index > range[0] && index < range[1]) {
            return arr[index];
        } else if (index < range[0]) {
            return bfprt(arr, L, range[0] - 1, index);
        } else {
            return bfprt(arr, range[1] + 1, R, index);
        }
    }

    // 精挑细选一个数
    // 过程：
    // 在arr[L...R] 五个数一组
    // 小组内排序
    // 每个小组中位数领出来，组成marr
    // 返回marr的中位数
    public static int medianOfMedians(int[]arr,int L,int R){
        int size = R-L+1;
        // 是否要补最后一组
        int offset = size%5==0?0:1;
        int[] marr = new int[size/5+offset];
        for (int temp = 0; temp < marr.length; temp++) {
            int tempFirst = L+temp*5;
            marr[temp] = getMedian(arr, tempFirst,Math.min(R,tempFirst+4));
        }
        return bfprt(marr, 0, marr.length - 1, marr.length / 2);
    }

    private static int getMedian(int[] arr, int L, int R) {
        inserionSort(arr,L,R);
        return arr[(L + R) / 2];
    }

    private static void inserionSort(int[] arr, int L, int R) {
        for (int i = L+1; i <=R; i++) {
            for (int j = i-1; j >=L&&arr[j]>arr[j+1]; j--) {
                ArrayUtils.exchangeElements(arr,j,j+1);
            }
        }
    }
    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int[] arr = new int[(int)(Math.random()*maxSize)+1];
        return null;
    }
}
